import java.util.ArrayList;
import java.util.List;

/*

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]

 */
public class addOperators {
    public List<String> addOperators1(String num, int target) {
        List<String> rst = new ArrayList<String>();
        if(num == null || num.length() == 0) return rst;
        helper(rst, "", num, target, 0, 0, 0);
        return rst;
    }
    public void helper(List<String> rst, String path, String num, int target, int pos, long eval, long multed){
        if(pos == num.length()){
            if(target == eval)
                rst.add(path);
            return;
        }
        for(int i = pos; i < num.length(); i++){
            //排除前导0的情况 出现前导0 并且无法长度大于0的情况 后续的位置都无效
            if(i != pos && num.charAt(pos) == '0') break;
            //防止大数溢出 可能会超过int的最大值
            long cur = Long.parseLong(num.substring(pos, i + 1));
            if(pos == 0){
                helper(rst, path + cur, num, target, i + 1, cur, cur);
            }
            else{
                //下一个计算如果是减法，下一个表达式的值为eval+cur
                //下一个表达式的乘法左前缀为cur
                helper(rst, path + "+" + cur, num, target, i + 1, eval + cur , cur);
                //下一个计算如果是减法，下一个表达式的值为eval-cur
                //下一个表达式的乘法左前缀为-cur
                helper(rst, path + "-" + cur, num, target, i + 1, eval -cur, -cur);
                //下一个计算如果是乘法，下一个表达式的值为eval - multed + multed * cur
                //下一个表达式的乘法左前缀为multed * cur
                helper(rst, path + "*" + cur, num, target, i + 1, eval - multed + multed * cur, multed * cur );
            }
        }
    }
    public void dfs(String path, int pos, long prefix,long eval, int tatget,String num,List<String> result){
         if(pos==num.length())
         {
             System.out.println("yes"+eval);
             if (tatget==eval)
                 result.add(path);
             return ;
         }
         for (int i=pos;i<num.length();i++)
         {
             if(i != pos && num.charAt(pos) == '0') break;
            long curl=Long.parseLong(num.substring(pos,i+1));

             if (pos==0)
             {
                 dfs(path+curl,i+1,curl,curl,tatget,num,result);
             }
             else
             //+
             {
                 dfs(path + "+" + curl, i + 1, curl, eval + curl, tatget, num, result);


                 //-
                 dfs(path + "-" + curl, i + 1, -curl, eval - curl, tatget, num, result);

                 //*
                 dfs(path + "*" + curl, i + 1, curl * prefix, eval - prefix + curl * prefix, tatget, num, result);
             }
         }
    }
    public List<String> addOperators2(String num, int target) {
        List<String> rst = new ArrayList<String>();
        if (num==null||num.length()==0)
            return rst;
        dfs("",0,0,0,target,num,rst);
        return rst;
    }
    public static void main(String[] args) {
        addOperators ad=new addOperators();
        //System.out.println(ad.addOperators2("00",0));
       // ad.addOperators2("12345",10);
    }
}

